//题目:
// 给你一个整数数组 nums 和一个整数 k 。你需要找到 nums 中长度为 k 的 子序列 ，且这个子序列的 和最大 。
// 请你返回 任意 一个长度为 k 的整数子序列。
// 子序列 定义为从一个数组里删除一些元素后，不改变剩下元素的顺序得到的数组。
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
//代码:
class Solution 
{
public:
    struct compare
    {
        bool operator()(const pair<int,int>& pir1, const pair<int,int> pir2)
        {
            return pir1.second>pir2.second;//建小根堆，排升序
        }
    };
    struct cmp
    {
        bool operator()(const pair<int,int>& pir1, const pair<int,int> pir2)
        {
            return pir1.first<pir2.first;//排升序
        }
    };
    vector<int> maxSubsequence(vector<int>& nums, int k) 
    {
        //题意转换：从nums数组中找到前k个最大元素，建小根堆，排升序，但需要记录各元素在nums中的相对位置
        
        //1.先按second建小根堆，排升序
        priority_queue<pair<int,int>,vector<pair<int,int>>,compare> heap;//key是元素在nums中的下标，value是元素值
        //2.元素插入
        for(int i=0;i<nums.size();i++)
        {
            heap.push(make_pair(i,nums[i]));
            if(heap.size()>k)heap.pop();//把数值最小的元素扔掉，保留的都是数值大的元素
        }
        //3.将剩余k个元素存放在vector中
        vector<pair<int,int>> v_pir;
        while(!heap.empty())
        {
            v_pir.push_back(heap.top());
            heap.pop();
        }
        //4.对v_pir中对元素按first排升序
        sort(v_pir.begin(),v_pir.end(),cmp());
        //5.提取结果
        vector<int> ret;
        for(int i=0;i<v_pir.size();i++)ret.push_back(v_pir[i].second);
        return ret;
    }
};